1. Field of the Invention
This invention relates to a communication system (“network”) and more particularly to a network of interconnected nodes and/or switches that allow fast decode or routing of packets within the network.
2. Description of the Related Art
A communication network is generally regarded as an interconnected set of subnetworks or subnets. The network can extend over localized subnets as an intranet, or can extend globally as an internet between one or more intranets. A communication network can therefore forward data within a localized network between termination devices extending to almost anywhere around the world. The termination devices include any data entry/retrieval system (e.g., telephone or computer), and a network includes a local and/or global interconnection of termination devices configured on one or more subnets.
The basic underpinnings of network operation is the various protocols used to communicate between termination devices. A popular foundation for those protocols is the Open System Interconnect (“OSI”) model. Using that model or a derivative thereof, protocols can be developed which work in concert with each other. A popular communication protocol includes the Transmission Control Protocol (“TCP”) and the Internet Protocol (“IP”). Protocols such as TCP/IP determine how the termination devices will communicate with each other over a network configured with or without internet connection.
Many popular protocols including TCP/IP deliver data across the network in the form of a packet. Each packet of a particular message may be sent across different routes of the network at the same time and then reassembled at the proper termination device. In order to ensure the packets are properly received, certain layers of the OSI protocol stack will wrap the data before the packet is sent across the network. For example, TCP can divide data into segments which are then placed into, for example, IP datagrams having a header which includes the IP address of the originating and receiving termination devices. The IP datagram and header is, therefore, a wrapped IP which gets further wrapped when transferring the IP wrapper from the network layer to the data link and physical layers. For example, the IP datagram can be further wrapped using a Point-to-Point Protocol (“PPP”), a popular such protocol being that which follows the Ethernet specification at the physical layer. Thus, it is not until the IP has been wrapped possibly several times will the TCP be forwarded across the network.
Coupled between subnets of a network are various classes of devices, including bridges, routers, and switches. Bridges and switches for the most part operate primarily in hardware and within the domain of the data link layer. Legacy routers, on the other hand, operate within the network layer and can be programmed and reconfigured to intelligently forward packets across the network according to the most optimal routing path. Although the distinction has become somewhat blurred with modern day network layer switches and bridges, it is still the primary intent that a switch and bridge be employed mostly in hardware. Based on configuration of the switch or bridge, all data packets received by a particular input port are routinely sent to any particular output port or ports. This operation can be quickly repeated each time a packet is received.
While switches are relatively fast and can send data from an input port to an output port with very little delay or lag time, switches do not have the capability to adapt to change in traffic conditions as do routers. Because routers can easily adapt to avoid traffic bottlenecks, routers employ look-up tables and fairly complex routing algorithms. Typical routers are based on a packet processor. The processor can be programmed to determine the most optimal connection between input and output ports of the router. Coupled to the processor is a memory bus and associated system memory, whereby routing tables can be stored in the system memory and are periodically fetched by the processor whenever a routing decision is to be made. Thus, when a packet is received on one port of the router, the processor will execute a look-up operation by fetching the appropriate table information from system memory. Most routing tables are dynamic, in that they constantly change as network traffic and conditions change, so that the processor can interconnect the ports in a way that is most efficient at that time. Dynamic routing tables can be built and re-built using various routing protocols, popular such protocols include Routing Information Protocol (“RIP”) and Exterior Gateway Protocol (“EGP”).
Periodically programming the routing tables may mean that one router on a network need not know the location of the physically closest router or its placement within the network. The router will simply route based on its existing routing table and the resulting look-up outcome. Such a system can be considered a non-relative or non-deterministic router topography. Non-deterministic routers tend to rely on the number of hops (i.e., the number of routers or gateways) when determining the most optimal routing path. Thus, while a router may know the number of additional routers on a given path, it does not necessarily know or have a link to the identity of those routers.
In most modern networks, a packet will travel more than 10 or 20 hops before arriving at its destination. As defined herein, a hop is equivalent to a traversal of a router or address translator. More specifically, a hop is defined as an operation that invokes a look-up or translation operation. When traveling across a network, a packet may be sent across numerous look-up or translation tables, and also through numerous switches, before arriving at its destination. Each of these look-up or translations adds to the latency of the packet transmission. It is generally recognized that transmission latency is lessened, and transmission bandwidth increased, if the number of hops is reduced. Therefore, it is desirable that the number of hops from one termination device to another termination device be minimal. This is due, in part, to the time-consumptive look-up (or address translation/modification) procedure performed by each router. Furthermore, since a particular router will not necessarily know the placement of all other routers of a network, each look-up table must include identification numbers or addresses for each of the other routers within the network—even those not within the optimal routing path. The destination address is compared against each of those identification numbers for each routing operation. If a network is quite large, the access times needed to perform a look-up from the packet processor to the system memory can be correspondingly long.
This problem is compounded with the advent of high-speed networks of one gigabits per second (Gb/s) or higher. Look-up techniques needed to render forwarding decisions on rather large look-up tables drastically reduces the benefits of using high speed networks. Many termination devices use high-speed physical media, such as Ethernet. Moreover, subnet loops which interconnect localized devices can use even higher speed signals such as, for example, Synchronous Optical Networks (“SONETs”).
If the IP packets enter the input port of a router more quickly than that router can process those packets, the packets are sent to an input queue. The router generally processes packets from the queue in the order in which they are received. If the number of packets received exceeds the capacity of the queue, packets may be lost and may need to be re-sent. If the comparison between the IP destination and the routing table takes a significant amount of time, then it may be likely that numerous packets may be lost. Frequency of lost data would increase when bursts of data are being sent. The time needed to re-send packets deleteriously hinders the overall throughput of the network.
To improve the throughput of the networks, industry uses switches that can switch the packet to destined port without performing table lookup. The path is typically pre-established and the packets are switched without routing. This speeds up the packet transmission at the cost of flexibility and adoptability provided by the routers. Typically, switches operate on layer 2 MAC (or Ethernet) addresses. Industry has introduced layer 3 switches that perform some layer 3 functions but not routing.
It would be of benefit to introduce an improved switch having switching speeds of a conventional switch yet also having the adaptability of a router. The improved switch would avoid the throughput constraints of a conventional packet processor and system memory interface and, more importantly, the detriments of an extensive look-up table. The desired switch would be even more beneficial if it could maintain backward compatibility with the OSI model, protocols of that model, and address resolution used by various Address Resolution Protocols (“ARP”). Still further, the improved switch should desirably be used in an overall network that is deterministic as to the relative topological placement of each switch within that network. Thus, the switch could determine if it should wrap (or strip) incoming packets as an end switch or should pass-through packets as an intermediate or pass-through switch, both switches advantageously performing those functions with minimal time delay.
Packet transmission over today's network rely on routing or switching packets using public domain addresses such as IP address or Ethernet addresses. This is analogous to using street addresses to sorting and routing mail before the introduction of zip codes. To increase the efficiency, post office introduced the concept of zip code for mail sorting and routing. Street addresses are only used to deliver the mail to the street address after mail has arrived at the final destination post office.
It will be beneficial to introduce a similar mechanism to packet transport function in the networking world. The new mechanism should be able to work with popular protocols and should not introduce additional complexities.
Each routing node within the network needs to keep the routing information of the entire network or subnet current at all times for proper operations. In large networks of today, the networks are not static and they change frequently. The IP addresses are mobile and users can access a network from different locations at different times. This necessitates complex routing protocols that communicate routing information across the network.
It will be beneficial to have a network that can be dynamic and yet not require complex routing protocols to keep the network current.